<!DOCTYPE html>
<html prefix="og: http://ogp.me/ns# article: http://ogp.me/ns/article# " lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>maximum-contiguous-subsequence | 绿萝间</title>
<link href="../assets/css/all-nocdn.css" rel="stylesheet" type="text/css">
<link href="../assets/css/ipython.min.css" rel="stylesheet" type="text/css">
<link href="../assets/css/nikola_ipython.css" rel="stylesheet" type="text/css">
<meta name="theme-color" content="#5670d4">
<meta name="generator" content="Nikola (getnikola.com)">
<link rel="alternate" type="application/rss+xml" title="RSS" href="../rss.xml">
<link rel="canonical" href="https://muxuezi.github.io/posts/maximum-contiguous-subsequence.html">
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
    tex2jax: {
        inlineMath: [ ['$','$'], ["\\(","\\)"] ],
        displayMath: [ ['$$','$$'], ["\\[","\\]"] ],
        processEscapes: true
    },
    displayAlign: 'center', // Change this to 'center' to center equations.
    "HTML-CSS": {
        styles: {'.MathJax_Display': {"margin": 0}}
    }
});
</script><!--[if lt IE 9]><script src="../assets/js/html5.js"></script><![endif]--><meta name="author" content="Tao Junjie">
<link rel="prev" href="kivy-ch3-sound-recorder-for-android.html" title="kivy-ch3-sound-recorder-for-android" type="text/html">
<link rel="next" href="frequentism-and-bayesianism-chs-iv.html" title="frequentism-and-bayesianism-chs-iv" type="text/html">
<meta property="og:site_name" content="绿萝间">
<meta property="og:title" content="maximum-contiguous-subsequence">
<meta property="og:url" content="https://muxuezi.github.io/posts/maximum-contiguous-subsequence.html">
<meta property="og:description" content="Kadane's Algorithm¶








Kadane's Algorithm is an O(n) algorithm for finding the maximum contiguous subsequence in a one-dimensional sequence.
Kadane算法是用于寻找一维数组最大连续子集，复杂度O(n)。



begin
    (maxSum,">
<meta property="og:type" content="article">
<meta property="article:published_time" content="2015-06-24T13:42:52+08:00">
<meta property="article:tag" content="CHS">
<meta property="article:tag" content="ipython">
<meta property="article:tag" content="Other">
<meta property="article:tag" content="Python">
</head>
<body>
<a href="#content" class="sr-only sr-only-focusable">Skip to main content</a>

<!-- Menubar -->

<nav class="navbar navbar-inverse navbar-static-top"><div class="container">
<!-- This keeps the margins nice -->
        <div class="navbar-header">
            <button type="button" class="navbar-toggle collapsed" data-toggle="collapse" data-target="#bs-navbar" aria-controls="bs-navbar" aria-expanded="false">
            <span class="sr-only">Toggle navigation</span>
            <span class="icon-bar"></span>
            <span class="icon-bar"></span>
            <span class="icon-bar"></span>
            </button>
            <a class="navbar-brand" href="https://muxuezi.github.io/">

                <span id="blog-title">绿萝间</span>
            </a>
        </div>
<!-- /.navbar-header -->
        <div class="collapse navbar-collapse" id="bs-navbar" aria-expanded="false">
            <ul class="nav navbar-nav">
<li>
<a href="../archive.html">Archive</a>
                </li>
<li>
<a href="../categories/">Tags</a>
                </li>
<li>
<a href="../rss.xml">RSS feed</a>

                
            </li>
</ul>
<ul class="nav navbar-nav navbar-right">
<li>
    <a href="maximum-contiguous-subsequence.ipynb" id="sourcelink">Source</a>
    </li>

                
            </ul>
</div>
<!-- /.navbar-collapse -->
    </div>
<!-- /.container -->
</nav><!-- End of Menubar --><div class="container" id="content" role="main">
    <div class="body-content">
        <!--Body content-->
        <div class="row">
            
            
<article class="post-text h-entry hentry postpage" itemscope="itemscope" itemtype="http://schema.org/Article"><header><h1 class="p-name entry-title" itemprop="headline name"><a href="#" class="u-url">maximum-contiguous-subsequence</a></h1>

        <div class="metadata">
            <p class="byline author vcard"><span class="byline-name fn">
                    Tao Junjie
            </span></p>
            <p class="dateline"><a href="#" rel="bookmark"><time class="published dt-published" datetime="2015-06-24T13:42:52+08:00" itemprop="datePublished" title="2015-06-24 13:42">2015-06-24 13:42</time></a></p>
            
        <p class="sourceline"><a href="maximum-contiguous-subsequence.ipynb" id="sourcelink">Source</a></p>

        </div>
        

    </header><div class="e-content entry-content" itemprop="articleBody text">
    <div tabindex="-1" id="notebook" class="border-box-sizing">
    <div class="container" id="notebook-container">

<div class="cell border-box-sizing text_cell rendered">
<div class="prompt input_prompt">
</div>
<div class="inner_cell">
<div class="text_cell_render border-box-sizing rendered_html">
<h2 id="Kadane's-Algorithm">
<a href="http://www.algorithmist.com/index.php/Kadane's_Algorithm">Kadane's Algorithm</a><a class="anchor-link" href="maximum-contiguous-subsequence.html#Kadane's-Algorithm">¶</a>
</h2>
</div>
</div>
</div>
<div class="cell border-box-sizing text_cell rendered">
<div class="prompt input_prompt">
</div>
<div class="inner_cell">
<div class="text_cell_render border-box-sizing rendered_html">
<p><strong>Kadane's Algorithm</strong> is an <em>O</em>(<em>n</em>) algorithm for finding the maximum contiguous <a href="../index.php/Subsequence" title="Subsequence">subsequence</a> in a one-dimensional <a href="../index.php/Sequence" title="Sequence">sequence</a>.</p>
<p><strong>Kadane算法</strong>是用于寻找一维<a href="../index.php/Sequence" title="Sequence">数组</a>最大连续<a href="../index.php/Subsequence" title="Subsequence">子集</a>，复杂度<em>O</em>(<em>n</em>)。</p>
<!-- TEASER_END -->


<pre><code>begin
    (maxSum, maxStartIndex, maxEndIndex) := (-INFINITY, 0, 0)
    currentMaxSum := 0
    currentStartIndex := 1
    for currentEndIndex := 1 to n do
        currentMaxSum := currentMaxSum + array[currentEndIndex]
        if currentMaxSum &gt; maxSum then
            (maxSum, maxStartIndex, maxEndIndex) := (currentMaxSum, currentStartIndex, currentEndIndex)
        endif

        if currentMaxSum &lt; 0 then
            currentMaxSum := 0
            currentStartIndex := currentEndIndex + 1
        endif
    endfor

    return (maxSum, maxStartIndex, maxEndIndex)
end</code></pre>

</div>
</div>
</div>
<div class="cell border-box-sizing code_cell rendered">
<div class="input">
<div class="prompt input_prompt">In [1]:</div>
<div class="inner_cell">
    <div class="input_area">
<div class=" highlight hl-ipython3"><pre><span></span><span class="k">def</span> <span class="nf">max_subarray</span><span class="p">(</span><span class="n">A</span><span class="p">):</span>
    <span class="n">maxSum</span><span class="p">,</span> <span class="n">maxStartIndex</span><span class="p">,</span> <span class="n">maxEndIndex</span> <span class="o">=</span> <span class="n">A</span><span class="p">[</span><span class="mi">0</span><span class="p">],</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span>
    <span class="n">currentMaxSum</span> <span class="o">=</span> <span class="mi">0</span>
    <span class="n">currentStartIndex</span> <span class="o">=</span> <span class="mi">0</span>
    <span class="k">for</span> <span class="n">currentEndIndex</span><span class="p">,</span> <span class="n">item</span> <span class="ow">in</span> <span class="nb">enumerate</span><span class="p">(</span><span class="n">A</span><span class="p">):</span>
        <span class="n">currentMaxSum</span> <span class="o">=</span> <span class="n">currentMaxSum</span> <span class="o">+</span> <span class="n">A</span><span class="p">[</span><span class="n">currentEndIndex</span><span class="p">]</span>
        <span class="k">if</span> <span class="n">currentMaxSum</span> <span class="o">&gt;</span> <span class="n">maxSum</span><span class="p">:</span>
            <span class="n">maxSum</span><span class="p">,</span> <span class="n">maxStartIndex</span><span class="p">,</span> <span class="n">maxEndIndex</span> <span class="o">=</span> <span class="n">currentMaxSum</span><span class="p">,</span> <span class="n">currentStartIndex</span><span class="p">,</span> <span class="n">currentEndIndex</span>
        <span class="k">if</span> <span class="n">currentMaxSum</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="p">:</span>
            <span class="n">currentMaxSum</span> <span class="o">=</span> <span class="mi">0</span>
            <span class="n">currentStartIndex</span> <span class="o">=</span> <span class="n">currentEndIndex</span> <span class="o">+</span> <span class="mi">1</span>
    <span class="k">return</span> <span class="p">(</span><span class="n">maxSum</span><span class="p">,</span> <span class="n">maxStartIndex</span><span class="p">,</span> <span class="n">maxEndIndex</span><span class="p">,</span> <span class="n">A</span><span class="p">[</span><span class="n">maxStartIndex</span><span class="p">:</span><span class="n">maxEndIndex</span><span class="o">+</span><span class="mi">1</span><span class="p">])</span>
</pre></div>

</div>
</div>
</div>

</div>
<div class="cell border-box-sizing code_cell rendered">
<div class="input">
<div class="prompt input_prompt">In [2]:</div>
<div class="inner_cell">
    <div class="input_area">
<div class=" highlight hl-ipython3"><pre><span></span><span class="n">x</span> <span class="o">=</span> <span class="p">[</span><span class="o">-</span><span class="mi">2</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="o">-</span><span class="mi">3</span><span class="p">,</span> <span class="mi">4</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="o">-</span><span class="mi">5</span><span class="p">,</span> <span class="mi">4</span><span class="p">]</span>
<span class="nb">print</span> <span class="sa">u</span><span class="s1">'最大连续子集：</span><span class="se">\n</span><span class="s1">和为</span><span class="si">{}</span><span class="s1">，起止下标</span><span class="si">{}</span><span class="s1">，</span><span class="si">{}</span><span class="s1">。</span><span class="se">\n</span><span class="s1">子集为</span><span class="si">{}</span><span class="s1">'</span><span class="o">.</span><span class="n">format</span><span class="p">(</span><span class="o">*</span><span class="n">max_subarray</span><span class="p">(</span><span class="n">x</span><span class="p">))</span>
</pre></div>

</div>
</div>
</div>

<div class="output_wrapper">
<div class="output">


<div class="output_area">
<div class="prompt"></div>
<div class="output_subarea output_stream output_stdout output_text">
<pre>最大连续子集：
和为6，起止下标3，6。
子集为[4, -1, 2, 1]
</pre>
</div>
</div>

</div>
</div>

</div>
<div class="cell border-box-sizing code_cell rendered">
<div class="input">
<div class="prompt input_prompt">In [1]:</div>
<div class="inner_cell">
    <div class="input_area">
<div class=" highlight hl-ipython3"><pre><span></span><span class="kn">from</span> <span class="nn">IPython.display</span> <span class="k">import</span> <span class="n">HTML</span>
<span class="n">HTML</span><span class="p">(</span><span class="s1">'&lt;iframe width="800" height="500" frameborder="0" src="http://pythontutor.com/iframe-embed.html#code=def+max_subarray(A)%3A%0D%0A++++maxSum,+maxStartIndex,+maxEndIndex+%3D+A%5B0%5D,+0,+0%0D%0A++++currentMaxSum+%3D+0%0D%0A++++currentStartIndex+%3D+0%0D%0A++++for+currentEndIndex,+item+in+enumerate(A)%3A%0D%0A++++++++currentMaxSum+%3D+currentMaxSum+%2B+A%5BcurrentEndIndex%5D%0D%0A++++++++if+currentMaxSum+</span><span class="si">%3E</span><span class="s1">+maxSum%3A%0D%0A++++++++++++maxSum,+maxStartIndex,+maxEndIndex+%3D+currentMaxSum,+currentStartIndex,+currentEndIndex%0D%0A++++++++if+currentMaxSum+%3C+0%3A%0D%0A++++++++++++currentMaxSum+%3D+0%0D%0A++++++++++++currentStartIndex+%3D+currentEndIndex+%2B+1%0D%0A++++return+(maxSum,+maxStartIndex,+maxEndIndex,+A%5BmaxStartIndex%3AmaxEndIndex%2B1%5D)%0D%0A++++%0D%0Ax+%3D+%5B-2,+1,+-3,+4,+-1,+2,+1,+-5,+4%5D%0D%0A%0D%0Amax_subarray(x)&amp;origin=opt-frontend.js&amp;cumulative=false&amp;heapPrimitives=false&amp;drawParentPointers=false&amp;textReferences=false&amp;showOnlyOutputs=false&amp;py=2&amp;rawInputLstJSON=%5B%5D&amp;curInstr=52&amp;codeDivWidth=350&amp;codeDivHeight=400"&gt; &lt;/iframe&gt;'</span><span class="p">)</span>
</pre></div>

</div>
</div>
</div>

<div class="output_wrapper">
<div class="output">


<div class="output_area">
<div class="prompt output_prompt">Out[1]:</div>

<div class="output_html rendered_html output_subarea output_execute_result">
<iframe width="800" height="500" frameborder="0" src="http://pythontutor.com/iframe-embed.html#code=def+max_subarray(A)%3A%0D%0A++++maxSum,+maxStartIndex,+maxEndIndex+%3D+A%5B0%5D,+0,+0%0D%0A++++currentMaxSum+%3D+0%0D%0A++++currentStartIndex+%3D+0%0D%0A++++for+currentEndIndex,+item+in+enumerate(A)%3A%0D%0A++++++++currentMaxSum+%3D+currentMaxSum+%2B+A%5BcurrentEndIndex%5D%0D%0A++++++++if+currentMaxSum+%3E+maxSum%3A%0D%0A++++++++++++maxSum,+maxStartIndex,+maxEndIndex+%3D+currentMaxSum,+currentStartIndex,+currentEndIndex%0D%0A++++++++if+currentMaxSum+%3C+0%3A%0D%0A++++++++++++currentMaxSum+%3D+0%0D%0A++++++++++++currentStartIndex+%3D+currentEndIndex+%2B+1%0D%0A++++return+(maxSum,+maxStartIndex,+maxEndIndex,+A%5BmaxStartIndex%3AmaxEndIndex%2B1%5D)%0D%0A++++%0D%0Ax+%3D+%5B-2,+1,+-3,+4,+-1,+2,+1,+-5,+4%5D%0D%0A%0D%0Amax_subarray(x)&amp;origin=opt-frontend.js&amp;cumulative=false&amp;heapPrimitives=false&amp;drawParentPointers=false&amp;textReferences=false&amp;showOnlyOutputs=false&amp;py=2&amp;rawInputLstJSON=%5B%5D&amp;curInstr=52&amp;codeDivWidth=350&amp;codeDivHeight=400"> </iframe>
</div>

</div>

</div>
</div>

</div>
<div class="cell border-box-sizing code_cell rendered">
<div class="input">
<div class="prompt input_prompt">In [ ]:</div>
<div class="inner_cell">
    <div class="input_area">
<div class=" highlight hl-ipython3"><pre><span></span> 
</pre></div>

</div>
</div>
</div>

</div>
    </div>
  </div>

    </div>
    <aside class="postpromonav"><nav><ul itemprop="keywords" class="tags">
<li><a class="tag p-category" href="../categories/chs.html" rel="tag">CHS</a></li>
            <li><a class="tag p-category" href="../categories/ipython.html" rel="tag">ipython</a></li>
            <li><a class="tag p-category" href="../categories/other.html" rel="tag">Other</a></li>
            <li><a class="tag p-category" href="../categories/python.html" rel="tag">Python</a></li>
        </ul>
<ul class="pager hidden-print">
<li class="previous">
                <a href="kivy-ch3-sound-recorder-for-android.html" rel="prev" title="kivy-ch3-sound-recorder-for-android">Previous post</a>
            </li>
            <li class="next">
                <a href="frequentism-and-bayesianism-chs-iv.html" rel="next" title="frequentism-and-bayesianism-chs-iv">Next post</a>
            </li>
        </ul></nav></aside><script type="text/javascript" src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"> </script><script type="text/x-mathjax-config">
MathJax.Hub.Config({
    tex2jax: {
        inlineMath: [ ['$','$'], ["\\(","\\)"] ],
        displayMath: [ ['$$','$$'], ["\\[","\\]"] ],
        processEscapes: true
    },
    displayAlign: 'center', // Change this to 'center' to center equations.
    "HTML-CSS": {
        styles: {'.MathJax_Display': {"margin": 0}}
    }
});
</script></article>
</div>
        <!--End of body content-->

        <footer id="footer">
            Contents © 2017         <a href="mailto:muxuezi@gmail.com">Tao Junjie</a> - Powered by         <a href="https://getnikola.com" rel="nofollow">Nikola</a>         
<a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0">
<img alt="Creative Commons License BY-NC-SA" style="border-width:0; margin-bottom:12px;" src="http://i.creativecommons.org/l/by-nc-sa/4.0/80x15.png"></a>
            
        </footer>
</div>
</div>


            <script src="../assets/js/all-nocdn.js"></script><script>$('a.image-reference:not(.islink) img:not(.islink)').parent().colorbox({rel:"gal",maxWidth:"100%",maxHeight:"100%",scalePhotos:true});</script><!-- fancy dates --><script>
    moment.locale("en");
    fancydates(0, "YYYY-MM-DD HH:mm");
    </script><!-- end fancy dates --><script>
  (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
  (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
  m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
  })(window,document,'script','//www.google-analytics.com/analytics.js','ga');

  ga('create', 'UA-51330059-1', 'auto');
  ga('send', 'pageview');

</script>
</body>
</html>
